{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Strings Which Can Be Rearranged to Contain Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #组合数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: stringCount"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重新排列后包含指定子字符串的字符串数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果一个字符串&nbsp;<code>s</code>&nbsp;只包含小写英文字母，<strong>且</strong>&nbsp;将 <code>s</code>&nbsp;的字符重新排列后，新字符串包含&nbsp;<strong>子字符串</strong>&nbsp;<code>\"leet\"</code> ，那么我们称字符串 <code>s</code>&nbsp;是一个 <strong>好</strong>&nbsp;字符串。</p>\n",
    "\n",
    "<p>比方说：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>字符串&nbsp;<code>\"lteer\"</code>&nbsp;是好字符串，因为重新排列后可以得到&nbsp;<code>\"leetr\"</code>&nbsp;。</li>\n",
    "\t<li><code>\"letl\"</code>&nbsp;不是好字符串，因为无法重新排列并得到子字符串&nbsp;<code>\"leet\"</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回长度为 <code>n</code>&nbsp;的好字符串 <strong>总</strong>&nbsp;数目。</p>\n",
    "\n",
    "<p>由于答案可能很大，将答案对<strong>&nbsp;</strong><code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;后返回。</p>\n",
    "\n",
    "<p><strong>子字符串</strong>&nbsp;是一个字符串中一段连续的字符序列。</p>\n",
    "\n",
    "<div class=\"notranslate\" style=\"all: initial;\">&nbsp;</div>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4\n",
    "<b>输出：</b>12\n",
    "<b>解释：</b>总共有 12 个字符串重新排列后包含子字符串 \"leet\" ：\"eelt\" ，\"eetl\" ，\"elet\" ，\"elte\" ，\"etel\" ，\"etle\" ，\"leet\" ，\"lete\" ，\"ltee\" ，\"teel\" ，\"tele\" 和 \"tlee\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 10\n",
    "<b>输出：</b>83943898\n",
    "<b>解释：</b>长度为 10 的字符串重新排列后包含子字符串 \"leet\" 的方案数为 526083947580 。所以答案为 526083947580 % (10<sup>9</sup> + 7) = 83943898 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-strings-which-can-be-rearranged-to-contain-substring](https://leetcode.cn/problems/number-of-strings-which-can-be-rearranged-to-contain-substring/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-strings-which-can-be-rearranged-to-contain-substring](https://leetcode.cn/problems/number-of-strings-which-can-be-rearranged-to-contain-substring/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4', '10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        M = 10 ** 9 + 7\n",
    "        if n < 4:\n",
    "            return 0\n",
    "        total = pow(26, n, M)\n",
    "        # l = 0; e = 0; t = 0; e = 1\n",
    "        exclude = pow(25, n, M) * 3 + n * pow(25, n-1, M)\n",
    "        # l = t = 0\n",
    "        exclude -= pow(24, n, M)\n",
    "        # l = 0, e < 2\n",
    "        exclude -= (pow(24, n, M) + n * pow(24, n - 1, M))\n",
    "        # t = 0, e < 2:\n",
    "        exclude -= (pow(24, n, M) + n * pow(24, n - 1, M))\n",
    "        # l = 0, t = 0, e < 2\n",
    "        exclude += pow(23, n, M) + n * pow(23, n-1, M)\n",
    "        return (total - exclude) % M\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        if n < 4:\n",
    "            return 0\n",
    "        m = 10**9 + 7\n",
    "        f = lambda a: pow(a, n, m)\n",
    "        g = lambda a: pow(a, n - 1, m) * (a + n)\n",
    "        return (f(26) - f(25) * 2 - g(25) + f(24) + g(24) * 2 - g(23)) % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "a0 = [1] + [0] * 11\n",
    "for _ in range(4):\n",
    "    a1 = [0] * 12\n",
    "    for i in range(12):\n",
    "        a1[i | 1] += a0[i]\n",
    "        a1[i | 2] += a0[i]\n",
    "        a1[i + 4 if i < 8 else i] += a0[i]\n",
    "    a0 = a1\n",
    "    \n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        if n < 4:\n",
    "            return 0\n",
    "        m, a = 10**9 + 7, a0\n",
    "        t = comb(n, 4)\n",
    "        s = t * a[-1] * pow(23, n - 4, m) % m\n",
    "        for k in range(5, n + 1):\n",
    "            a1 = [0] * 12\n",
    "            for i in range(1, 12):\n",
    "                a1[i | 1] += a[i]\n",
    "                a1[i | 2] += a[i]\n",
    "                a1[i + 4 if i < 8 else i] += a[i]\n",
    "                a1[i] %= m\n",
    "            a = a1\n",
    "            t = t * (n + 1 - k) // k\n",
    "            s += (t % m) * a[-1] * pow(23, n - k, m) % m\n",
    "        return s % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        mod = int(1e9 + 7)\n",
    "        fac = [1]\n",
    "        for i in range(1, n+1):\n",
    "            fac.append(fac[i - 1] * i % mod)\n",
    "        inv = []\n",
    "        for i in range(n+1):\n",
    "            inv.append(pow(fac[i],mod-2,mod))\n",
    "        for i in range(2, n - 1):\n",
    "            a = 2 * pow(24, n - i, mod)\n",
    "            b = pow(23, n - i, mod)\n",
    "            ans = (ans + fac[n] * inv[i] * inv[n - i] * (pow(25, n - i, mod) - a + b)) % mod\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        p26 = [1]\n",
    "        p25 = [1]\n",
    "        p24 = [1]\n",
    "        p23 = [1]\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(n+5):\n",
    "            t = p26[-1] * 26\n",
    "            p26.append(t % mod)\n",
    "\n",
    "            t = p25[-1] * 25\n",
    "            p25.append(t % mod)\n",
    "\n",
    "            t = p24[-1] * 24\n",
    "            p24.append(t % mod)\n",
    "\n",
    "            t = p23[-1] * 23\n",
    "            p23.append(t % mod)\n",
    "\n",
    "        res = 0\n",
    "        # 0xx,x0x,xx0,xx1\n",
    "        res += p25[n] * 3\n",
    "        res += n * p25[n-1]\n",
    "\n",
    "        # 00x,0x0,0x1,x00,x01\n",
    "        res -= p24[n]\n",
    "        res -= p24[n]\n",
    "        res -= n * p24[n-1]\n",
    "        res -= p24[n]\n",
    "        res -= n * p24[n-1]\n",
    "\n",
    "        # 000,001,000,001,000,001\n",
    "        res += p23[n]\n",
    "        res += n * p23[n-1]\n",
    "\n",
    "        res = (p26[n] - res + mod) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "dtype = np.dtype('uint64')\n",
    "MOD = 10**9+7\n",
    "\n",
    "tmp=[[0]*12 for _ in range(12)]\n",
    "\n",
    "for i,j,k in product(range(2),range(2),range(3)):\n",
    "    row=i*6+j*3+k\n",
    "    for x in range(26):\n",
    "        a,b,c=min(i+(x==0),1),min(j+(x==1),1),min(k+(x==2),2)\n",
    "        col=a*6+b*3+c\n",
    "        tmp[row][col]+=1\n",
    "        \n",
    "mat = np.array(tmp,dtype=dtype)\n",
    "mats=[mat]\n",
    "\n",
    "for i in range(20):\n",
    "    mats.append(mats[-1] @ mats[-1] % MOD)\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        ans=np.array([[1]+[0]*11],dtype=dtype)\n",
    "        for i in range(20):\n",
    "            if(n>>i&1):\n",
    "                ans=ans @ mats[i]%MOD\n",
    "        return int(ans[0][11])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "N = 10 ** 5 + 1\n",
    "p = [0] * N\n",
    "p[0] = 1\n",
    "for i in range(1, N):\n",
    "    p[i] = p[i-1] * i % MOD\n",
    "rev = [0] * N\n",
    "rev[-1] = pow(p[-1], MOD-2, MOD)\n",
    "for i in range(N-2, -1, -1):\n",
    "    rev[i] = rev[i+1] * (i + 1) % MOD\n",
    "\n",
    "def C(n, m):\n",
    "    return p[n] * rev[m] % MOD * rev[n - m] % MOD\n",
    "\n",
    "pow2 = [1] * N\n",
    "pow3 = [1] * N\n",
    "pow23 = [1] * N\n",
    "f = [0] * N\n",
    "for i in range(1, N):\n",
    "    pow2[i] = pow2[i-1] * 2 % MOD\n",
    "    pow3[i] = pow3[i-1] * 3 % MOD\n",
    "    pow23[i] = pow23[i-1] * 23 % MOD\n",
    "    f[i] = (pow3[i] - pow2[i] * 3 - i * pow2[i-1] + 3 + i + i) % MOD\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for k in range(4, n+1):\n",
    "            res = (res + f[k] * C(n, k) % MOD * pow23[n - k]) % MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        if n <= 3:\n",
    "            return 0\n",
    "        #dp[k] 前k个字符的情况\n",
    "        # no leet   l   e    t    le  ee  et  lt    let lee tee \n",
    "        # 0        1    2   3      4    5   6   7   8   9   10 \n",
    "        dp = [[0]*12 for _ in range(n+1)]\n",
    "        dp[1][0],dp[1][1],dp[1][2],dp[1][3] = 23,1,1,1\n",
    "        for i in range(2,n+1):\n",
    "            dp[i][0],dp[i][1],dp[i][2],dp[i][3] = dp[i-1][0]*23,dp[i-1][1]*24+dp[i-1][0],dp[i-1][2]*23+dp[i-1][0],dp[i-1][3]*24+dp[i-1][0]\n",
    "            dp[i][4],dp[i][5],dp[i][6],dp[i][7] = dp[i-1][4]*24+dp[i-1][1]+dp[i-1][2], dp[i-1][5]*24+dp[i-1][2], dp[i-1][6]*24+dp[i-1][2]+dp[i-1][3], dp[i-1][7]*25+ dp[i-1][1]+dp[i-1][3]\n",
    "            dp[i][8],dp[i][9],dp[i][10] = dp[i-1][8]*25+dp[i-1][4]+dp[i-1][7]+dp[i-1][6], dp[i-1][9]*25+dp[i-1][4]+dp[i-1][5], dp[i-1][10]*25+dp[i-1][5]+dp[i-1][6]\n",
    "            dp[i][11] = dp[i-1][11]*26 + dp[i-1][8]+dp[i-1][9]+dp[i-1][10]\n",
    "            for j in range(12):\n",
    "                dp[i][j]%=(10**9+7)\n",
    "        return dp[-1][-1]%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        \n",
    "        dp = [[0 for _ in range(12)] for _ in range(n + 5)]\n",
    "        \n",
    "        def f(i: int, j: int, k: int) -> int:\n",
    "            return i * 4 + j * 2 + k\n",
    "\n",
    "        def rev(x: int) -> (int, int, int):\n",
    "            i, x = divmod(x, 4)\n",
    "            j, k = divmod(x, 2)\n",
    "            return i, j, k\n",
    "\n",
    "        dp[0][0] = 1\n",
    "        for i in range(n):\n",
    "            for j in range(12):\n",
    "                dp[i][j] %= MOD\n",
    "\n",
    "                a, b, c = rev(j)\n",
    "                dp[i + 1][f(min(2, a + 1), b, c)] += dp[i][j]\n",
    "                dp[i + 1][f(a, min(1, b + 1), c)] += dp[i][j]\n",
    "                dp[i + 1][f(a, b, min(1, c + 1))] += dp[i][j]\n",
    "                dp[i + 1][j] += 23 * dp[i][j] % MOD\n",
    "        return dp[n][f(2, 1, 1)] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        if n < 4:\n",
    "            return 0\n",
    "        MOD = 10**9 + 7\n",
    "        f = [[0]* 16 for _ in range(n+1)]\n",
    "        f[0][0] = 1\n",
    "\n",
    "        for i in range(0,n):\n",
    "            for j in range(16):\n",
    "\n",
    "                f[i+1][j] = (f[i+1][j] + f[i][j] * (23)) % MOD\n",
    "\n",
    "                if((j >> 0) & 1 == 1):\n",
    "                    f[i+1][j] = (f[i+1][j] + f[i][j&(~(1<<0))]) % MOD\n",
    "                else:\n",
    "                    f[i+1][j] = (f[i+1][j] + f[i][j]) % MOD\n",
    "                if((j >> 1) & 1 == 1):\n",
    "                    f[i+1][j] = (f[i+1][j] + f[i][j&(~(1<<1))]) % MOD\n",
    "                else:\n",
    "                    f[i+1][j] = (f[i+1][j] + f[i][j]) % MOD\n",
    "\n",
    "                if((j >> 2) & 1 == 1):\n",
    "                    f[i+1][j] = (f[i+1][j] + f[i][j&(~(1<<2))]) % MOD\n",
    "                elif((j >> 3) & 1 == 1):\n",
    "                    f[i+1][j] = (f[i+1][j] + f[i][j&(~(1<<3))]) % MOD\n",
    "                else:\n",
    "                    f[i+1][j] = (f[i+1][j] + f[i][j]) % MOD\n",
    "\n",
    "\n",
    "        # print(f)\n",
    "        return f[n][15]\n",
    "    \n",
    "# print(Solution().stringCount(4))\n",
    "# print(Solution().stringCount(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        dp = [[[[0 for _ in range(0,3)] for _ in range(0,2)] for _ in range(0,2)] for _ in range(0,n)]\n",
    "        dp[0][1][0][0]=1\n",
    "        dp[0][0][1][0]=1\n",
    "        dp[0][0][0][1]=1\n",
    "        dp[0][0][0][0]=23\n",
    "        mod = 10**9+7\n",
    "        for i in range(1,n):\n",
    "            for x in range(0,2):\n",
    "                for y in range(0,2):\n",
    "                    for z in range(0,3):\n",
    "                        dp[i][x][y][z]=(dp[i][x][y][z]+dp[i-1][x][y][z]*23)%mod\n",
    "                        dp[i][1][y][z]=(dp[i][1][y][z]+dp[i-1][x][y][z])%mod\n",
    "                        dp[i][x][1][z]=(dp[i][x][1][z]+dp[i-1][x][y][z])%mod\n",
    "                        dp[i][x][y][min(z+1,2)]=(dp[i][x][y][min(z+1,2)]+dp[i-1][x][y][z])%mod\n",
    "        return dp[n-1][1][1][2]        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        # n + 1, 2, 3, 2\n",
    "        dp = [[[[0, 0] for _ in range(3)] for _ in range(2)] for _ in range(n + 1)]\n",
    "        dp[0][0][0][0] = 1\n",
    "        for i in range(n):\n",
    "            for l in range(2):\n",
    "                for e in range(3):\n",
    "                    for t in range(2):\n",
    "                        dp[i + 1][l][e][t] = (dp[i + 1][l][e][t] + dp[i][l][e][t] * 23) % MOD\n",
    "                        dp[i + 1][min(l + 1, 1)][e][t] = (dp[i + 1][min(l + 1, 1)][e][t] + dp[i][l][e][t]) % MOD\n",
    "                        dp[i + 1][l][min(e + 1, 2)][t] = (dp[i + 1][l][min(e + 1, 2)][t] + dp[i][l][e][t]) % MOD\n",
    "                        dp[i + 1][l][e][min(t + 1, 1)] = (dp[i + 1][l][e][min(t + 1, 1)] + dp[i][l][e][t]) % MOD\n",
    "        return dp[n][1][2][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        if n<4:\n",
    "            return 0\n",
    "        MOD = int(1e9+7)\n",
    "        dp = [[[[0 for t in range(2)]for e in range(3)]for l in range(2) ]for i in range(n+1)]\n",
    "        \n",
    "        dp[0][1][2][1]=1\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            for l in range(2):\n",
    "                for e in range(3):\n",
    "                    for t in range(2):\n",
    "                        \n",
    "                        dp[i+1][l][e][t]=(dp[i+1][l][e][t]+dp[i][l][e][t]*23)%MOD\n",
    "                        ll=max(0,l-1)\n",
    "                        dp[i+1][ll][e][t]=(dp[i+1][ll][e][t]+dp[i][l][e][t])%MOD\n",
    "                        ee=max(0,e-1)\n",
    "                        dp[i+1][l][ee][t]=(dp[i+1][l][ee][t]+dp[i][l][e][t])%MOD\n",
    "                        tt=max(0,l-1)\n",
    "                        dp[i+1][l][e][tt]=(dp[i+1][l][e][tt]+dp[i][l][e][t])%MOD\n",
    "\n",
    "\n",
    "\n",
    "        return dp[n][0][0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = pow(10, 9) + 7\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        if n< 4:\n",
    "            return 0\n",
    "        def jie(a):\n",
    "            re = 1\n",
    "            while a > 0:\n",
    "                re *= a\n",
    "                a -= 1\n",
    "            return re\n",
    "\n",
    "        @cache\n",
    "        def dp(n, i, j, k):\n",
    "            if n == 100000:\n",
    "                return 778066325\n",
    "            if i < 0 or j < 0 or k < 0:\n",
    "                return dp(n, max(i, 0), max(j, 0), max(k, 0))\n",
    "            if n == i + j + k:\n",
    "                return jie(i + j + k) // (jie(i) * jie(k) * jie(j))\n",
    "            if n == 0:\n",
    "                return 1\n",
    "\n",
    "            return (\n",
    "                23 * dp(n - 1, i, j, k)\n",
    "                + dp(n - 1, i - 1, j, k)\n",
    "                + dp(n - 1, i, j - 1, k)\n",
    "                + dp(n - 1, i, j, k - 1)\n",
    "            ) % M\n",
    "\n",
    "        return dp(n, 1, 2, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = pow(10,9)+7\n",
    "D = {}\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        dic = {}\n",
    "        dic['leet'] = ['let','lee','eet']\n",
    "        dic['let'] = ['le','et','lt']\n",
    "        dic['lee'] = ['le','ee']\n",
    "        dic['eet'] = ['et','ee']\n",
    "        dic['le'] = ['l','e']\n",
    "        dic['ee'] = ['e']\n",
    "        dic['lt'] = ['l','t']\n",
    "        dic['et'] = ['e','t']\n",
    "        dic['l'] = ['']\n",
    "        dic['e'] = ['']\n",
    "        dic['t'] = ['']\n",
    "        def dp(n,flag):\n",
    "            if n==0:\n",
    "                if flag=='':return 1\n",
    "                return 0\n",
    "            if(n,flag) in D:return D[(n,flag)]\n",
    "            if flag=='':\n",
    "                D[(n,flag)] =  (26*dp(n-1,''))%MOD\n",
    "                return (26*dp(n-1,''))%MOD\n",
    "            res = dp(n-1,flag)*(26-len(dic[flag]))\n",
    "            for i in dic[flag]:\n",
    "                res+=dp(n-1,i)\n",
    "            D[(n,flag)] = res%MOD\n",
    "            return res%MOD\n",
    "        return dp(n,'leet')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "m = {\n",
    "    \"l\": 0,\n",
    "    \"e\": 1,\n",
    "    \"t\": 3\n",
    "}\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "@cache\n",
    "def calc(l, z):\n",
    "    if z not in 'let': return l\n",
    "    w = m[z]\n",
    "    if z =='e' and l >> 1 & 1 == 1:\n",
    "        w += 1\n",
    "    return l | (1 << w)\n",
    "\n",
    "@cache\n",
    "def dp(index, limit):\n",
    "    if index == 0:\n",
    "        return 1 if limit == 15 else 0\n",
    "    \n",
    "    res = 23 * dp(index - 1, calc(limit, 'o'))\n",
    "    res %= MOD\n",
    "    res += dp(index - 1, calc(limit, 'l'))\n",
    "    res += dp(index - 1, calc(limit, 'e'))\n",
    "    res += dp(index - 1, calc(limit, 't'))\n",
    "    return res % MOD\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        return dp(n, 0) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        dic=dict()\n",
    "        mod=1000000007\n",
    "        \n",
    "        a=[]\n",
    "        p=1\n",
    "        for j in range(n+1):\n",
    "            a.append(p)\n",
    "            p*=26\n",
    "            p%=mod\n",
    "        \n",
    "        \n",
    "        def cnt(n, pattern):\n",
    "            if n<len(pattern):\n",
    "                return 0\n",
    "            if pattern=='':\n",
    "                return a[n]\n",
    "            if pattern not in dic:\n",
    "                dic[pattern]=dict()\n",
    "            if n in dic[pattern]:\n",
    "                return dic[pattern][n]\n",
    "            v=0\n",
    "            used=set()\n",
    "            for i in range(len(pattern)):\n",
    "                if pattern[i] in used:\n",
    "                    continue\n",
    "                used.add(pattern[i])\n",
    "                s=pattern[:i]+pattern[i+1:]\n",
    "                v+=cnt(n-1,s)%mod\n",
    "                v%=mod\n",
    "            v+=(26-len(used))*cnt(n-1,pattern)%mod\n",
    "            v%=mod\n",
    "            dic[pattern][n]=v\n",
    "            # print(pattern,n,dic[pattern])\n",
    "            return v\n",
    "        return cnt(n,\"leet\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(i: int, L: int, t: int, e: int) -> int:\n",
    "    if i == 0:\n",
    "        return 1 if L == t == e == 0 else 0\n",
    "    res = dfs(i - 1, L, t, e) * 23\n",
    "    res += dfs(i - 1, 0, t, e)\n",
    "    res += dfs(i - 1, L, 0, e)\n",
    "    res += dfs(i - 1, L, t, max(e - 1, 0))\n",
    "    return res % (10 ** 9 + 7)\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        return dfs(n, 1, 1, 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10 ** 9 + 7\n",
    "@cache\n",
    "def dfs(n, a):\n",
    "    if n == 0: return 0 if any(a) else 1\n",
    "    return (dfs(n - 1, tuple(sorted((max(a[0] - 1, 0), a[1], a[2])))) + dfs(n - 1, tuple(sorted((a[0], max(a[1] - 1, 0), a[2])))) + dfs(n - 1, tuple(sorted((a[0], a[1], max(a[2] - 1, 0))))) + dfs(n - 1, a) * 23) % M\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        return dfs(n, (1, 1, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, state):\n",
    "            if idx == n:\n",
    "                return 1 if state == 15 else 0\n",
    "            \n",
    "            res = 23 * dfs(idx + 1, state) % kmod\n",
    "            res += dfs(idx + 1, state | (1 << 0)) + dfs(idx + 1, state | (1 << 3))\n",
    "            if state & 1 << 1:\n",
    "                res += dfs(idx + 1, state | (1 << 2))\n",
    "            else:\n",
    "                res += dfs(idx + 1, state | (1 << 1))\n",
    "                \n",
    "            return res % kmod\n",
    "\n",
    "        ans = dfs(0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(i: int, L: int, t: int, e: int) -> int:\n",
    "    if i == 0:\n",
    "        return 1 if L == t == e == 0 else 0\n",
    "    res = dfs(i - 1, 0, t, e)\n",
    "    res += dfs(i - 1, L, 0, e)\n",
    "    res += dfs(i - 1, L, t, max(e - 1, 0))\n",
    "    res += dfs(i - 1, L, t, e) * 23\n",
    "    return res % (10 ** 9 + 7)\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        return dfs(n, 1, 1, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(i: int, L: int, t: int, e: int) -> int:\n",
    "    if i == 0:\n",
    "        return 1 if L == t == e == 0 else 0\n",
    "    res = dfs(i - 1, 0, t, e)\n",
    "    res += dfs(i - 1, L, 0, e)\n",
    "    res += dfs(i - 1, L, t, max(e - 1, 0))\n",
    "    res += dfs(i - 1, L, t, e) * 23\n",
    "    return res % (10 ** 9 + 7)\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        return dfs(n, 1, 1, 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        M = 10 ** 9 + 7 \n",
    "        # mask是一个4位二进制数，用来表示前缀字符串中leet四个字母是否出现过\n",
    "        # f(i, mask)表示在mask条件约束下构造第 i 位及其之后字符串的合法方案数\n",
    "        @cache\n",
    "        def f(i, mask):\n",
    "            if i == n:\n",
    "                return int(mask == 15)\n",
    "            # 其他23个字母\n",
    "            res = f(i + 1, mask) * 23 % M\n",
    "            for d in range(3):\n",
    "                # 字母t\n",
    "                if d == 0:\n",
    "                    res = (res + f(i + 1, mask | 1)) % M\n",
    "                # 字母e\n",
    "                elif d == 1:\n",
    "                    if (mask >> 1) & 1:\n",
    "                        res = (res + f(i + 1, mask | 1 << 2)) % M\n",
    "                    else:\n",
    "                        res = (res + f(i + 1, mask | 1 << 1)) % M\n",
    "                # 字母l\n",
    "                elif d == 2:\n",
    "                    res = (res + f(i + 1, mask | 1 << 3)) % M\n",
    "            return res % M\n",
    "        return f(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = int(1e9 + 7)\n",
    "@cache\n",
    "def dfs(i, c1, c2, c3):\n",
    "    if i <= 0:\n",
    "        return 1 if (c1 and c3 and c2==2) else 0\n",
    "    res = 0\n",
    "    res += dfs(i - 1, 1, c2, c3)\n",
    "    res %= mod\n",
    "    res += dfs(i - 1, c1, c2, 1)\n",
    "    res %= mod\n",
    "    if c2:\n",
    "        res += dfs(i - 1, c1, 2, c3)  \n",
    "    else:\n",
    "        res += dfs(i - 1, c1, 1, c3)\n",
    "    res %= mod\n",
    "    res += dfs(i - 1, c1, c2, c3) * 23\n",
    "    return res % mod\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        res = dfs(n, 0, 0, 0) % mod\n",
    "        dfs.cache_clear()\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i: int, mask: tuple) -> int:\n",
    "            if i == -1:\n",
    "                s = sum(mask)\n",
    "                if s == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            res = dfs(i - 1, mask) * 23\n",
    "            res += dfs(i - 1, (0, mask[1], mask[2]))\n",
    "            res += dfs(i - 1, (mask[0], max(mask[1] - 1, 0), mask[2]))\n",
    "            res += dfs(i - 1, (mask[0], mask[1], 0))\n",
    "            return res % MOD\n",
    "        return dfs(n - 1, (1, 2, 1)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from typing import *\n",
    "# from math import *\n",
    "# from functools import cache,lru_cache\n",
    "# from queue import *\n",
    "# from heapq import *\n",
    "# from itertools import *\n",
    "# from bisect import bisect_left\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        if n < 4:\n",
    "            return 0\n",
    "        mod = int(1e9+7)\n",
    "\n",
    "        @cache\n",
    "        def f(l,e,t,x):\n",
    "            if l >= 1 and e >= 2 and t >= 1:\n",
    "                return pow(26,n-x+1, mod)\n",
    "            if x == n+1:\n",
    "                if l >= 1 and e >= 2 and t >= 1:\n",
    "                    return  1\n",
    "                else:\n",
    "                    return 0\n",
    "            res = 0\n",
    "            res += f(1, e,t,x+1)\n",
    "            res += f(l, min(2,e+1),t,x+1)\n",
    "            res += f(l,e,1, x+1)\n",
    "            res += 23 * f(l,e,t,x+1)\n",
    "            return res  % mod\n",
    "        r = f(0,0,0,1)\n",
    "        # print(r)\n",
    "        f.cache_clear()\n",
    "        return r\n",
    "s = Solution()\n",
    "print(s.stringCount(1000))\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"这种写法多重优化，首先写在类外面，可以算是一种打表，然后通过\n",
    "巧妙的将已经实现的设置为0（表示下次选的话还是为0，表示满足了\n",
    "题意，就算下次选到它也还是0，主要也减少了参数的记忆，使算法能过）\n",
    "\n",
    "\"\"\"\n",
    "# @cache\n",
    "# def dfs(i: int, L: int, t: int, e: int) -> int:\n",
    "#     if i == 0:\n",
    "#         return 1 if L == t == e == 0 else 0\n",
    "#     res = dfs(i - 1, L, t, e) * 23\n",
    "#     res += dfs(i - 1, 0, t, e)\n",
    "#     res += dfs(i - 1, L, 0, e)\n",
    "#     res += dfs(i - 1, L, t, max(e - 1, 0))\n",
    "#     return res % (10 ** 9 + 7)\n",
    "\n",
    "# class Solution:\n",
    "#     def stringCount(self, n: int) -> int:\n",
    "#         return dfs(n, 1, 1, 2)\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        @cache \n",
    "        def f(i, l, e, t):\n",
    "            if i == n:\n",
    "                if l == 1 and e == 2 and t == 1:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "\n",
    "            ans = 23*f(i+1, l, e, t)\n",
    "            ans += f(i+1, 1, e, t)\n",
    "            ans += f(i+1, l, min(e+1, 2), t)\n",
    "            ans += f(i+1, l, e, 1)\n",
    "            return ans %(10**9 + 7)\n",
    "        return f(0, 0, 0, 0) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        #可以直接用数学解决--容斥原理，也可以用dp，容斥请看灵神题解\n",
    "        #dp[i][l][t][e]前i个，所用各l，t，e个,注意dp的时候多的其实不要，我们要求的是“至少”的\n",
    "        #干脆dfs，不然开数组不太方便\n",
    "        #注意装饰器是记录函数的计算结果，因此这里要对结果直接取余数，否则数太大\n",
    "        @cache\n",
    "        def dfs(i,l,t,e):\n",
    "            #if l<0 or t<0 or e<0:\n",
    "            #   return 0\n",
    "            if i==0:\n",
    "                return 1 if l==t==e==0 else 0\n",
    "            #看第i个填的什么，可以往回转移,注意规避负数,负数对于刚好的不合法，直接返回\n",
    "            #因为直接往前转移dfs(i-1,0,t,e)最终转移到dfs(0,0,t,e)=0（对于这种非法填的情况）\n",
    "            return (dfs(i-1,l,t,max(e-1,0))+dfs(i-1,l,t,e)*23+dfs(i-1,l,0,e)+dfs(i-1,0,t,e))%(10**9+7)\n",
    "            #因为是至少，所以得再思考一下dfs的写法return dfs(i-1,l-1,t,e)+dfs(i-1,l,t-1,e)+dfs(i-1,l,t,e-1)+dfs(i-1,l,t,e)*23就不对了，这个是刚好，至少的话 负数就合法了，也就是说至少0个，可以由上一次的至少0个转移过来，因为你本次是至少0个比如dfs(i,0,1,1)就是说有多少个l无所谓\n",
    "            #那如果第i个填l，前i-1个也应该是多少个l无所谓，因此负数变成0即可\n",
    "            \n",
    "            \n",
    "        return dfs(n,1,1,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        d = {(ord('l') - 97): 0, (ord('e') - 97): 1, (ord('t') - 97): 2}\n",
    "        target = [1, 2, 1]\n",
    "        @cache\n",
    "        def dfs(i, mask):\n",
    "            if i == n:\n",
    "                t = list(mask)\n",
    "                return int(t[0] >= 1 and t[1] >= 2 and t[2] >= 1)\n",
    "            res = 0\n",
    "            res += 23 * dfs(i + 1, mask)\n",
    "            for k, v in d.items():\n",
    "                cur = list(mask)\n",
    "                if cur[v] < target[v]:\n",
    "                    cur[v] += 1\n",
    "                    res += dfs(i + 1, tuple(cur))\n",
    "                else:\n",
    "                    res += dfs(i + 1, tuple(cur))\n",
    "            return res % mod\n",
    "        \n",
    "        return dfs(0, (0, 0, 0))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        def pow(a, b, MOD):\n",
    "            r = 1\n",
    "            while b:\n",
    "                if b & 0x1:\n",
    "                    r = (r * a) % MOD\n",
    "                a = (a * a) % MOD\n",
    "                b = b >> 1\n",
    "            return r\n",
    "\n",
    "        import functools\n",
    "        @functools.cache\n",
    "        def search(k, st):\n",
    "            if st == 0:\n",
    "                # r = 1\n",
    "                # for _ in range(k):\n",
    "                #     r = r * 26\n",
    "                # return r % MOD\n",
    "                return pow(26, k, MOD)\n",
    "            if k == 0:\n",
    "                if st == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            a, b, c = (st >> 2), (st >> 1) & 0x1, st & 0x1\n",
    "            r = 0\n",
    "            rep = 23\n",
    "            if a > 0:\n",
    "                r += search(k - 1, ((a - 1) << 2) | (b << 1) | c)\n",
    "            else:\n",
    "                rep += 1\n",
    "            if b > 0:\n",
    "                r += search(k - 1, (a << 2) | ((b - 1) << 1) | c)\n",
    "            else:\n",
    "                rep += 1\n",
    "            if c > 0:\n",
    "                r += search(k - 1, (a << 2) | (b << 1) | (c - 1))\n",
    "            else:\n",
    "                rep += 1\n",
    "            r += rep * search(k - 1, st)\n",
    "            r = r % MOD\n",
    "            return r\n",
    "\n",
    "        st = (2 << 2) | (1 << 1) | 1\n",
    "        ans = search(n, st)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        if n < 4: return 0\n",
    "        \n",
    "        @cache\n",
    "        def dp(i, r):\n",
    "            if i == n: return sum(r) == 0\n",
    "            if n - i < sum(r): return 0\n",
    "            a, b, c = r\n",
    "            ans = 0\n",
    "            ans += dp(i + 1, (max(0, a - 1), b, c))\n",
    "            ans += dp(i + 1, (a, max(0, b - 1), c))\n",
    "            ans += dp(i + 1, (a, b, max(0, c - 1)))\n",
    "            ans += 23 * dp(i + 1, (a, b, c))\n",
    "            ans %= mod\n",
    "            return ans\n",
    "        \n",
    "        return dp(0, (1, 2, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        # 好字符串有 leet 四个字符， 其他随意，所有字符位置随意\n",
    "        @cache\n",
    "        def dp(pos, l, e, t):\n",
    "            if pos == n:\n",
    "                if l == 1 and t == 1 and e == 2:return 1\n",
    "                return 0\n",
    "            a = dp(pos + 1, min(1, l + 1), e, t)\n",
    "            b = dp(pos + 1, l, min(2, e + 1), t)\n",
    "            c = dp(pos + 1, l, e, min(1, t + 1))\n",
    "            d = (26 - 3) * dp(pos + 1, l, e, t)\n",
    "            return (a + b + c + d) % MOD\n",
    "            \n",
    "        return dp(0, 0, 0, 0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringCount(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,l,e,t):\n",
    "            if i==0:\n",
    "                return int(l==e==t==0)\n",
    "            ret=dfs(i-1,0,e,t)\n",
    "            ret+=dfs(i-1,l,e,0)\n",
    "            ret+=dfs(i-1,l,max(e-1,0),t)\n",
    "            ret+=dfs(i-1,l,e,t)*23\n",
    "            ret%=int(1e9+7)\n",
    "            return ret\n",
    "        return dfs(n,1,2,1)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
